package com.zhanghp.class032;

/**
 * 位图的实现
 * <br/>
 * Bitset是一种能以紧凑形式存储位的数据结构
 * <br/>
 * Bitset(int n) : 初始化n个位，所有位都是0
 * <br/>
 * void fix(int i) : 将下标i的位上的值更新为1
 * <br/>
 * void unfix(int i) : 将下标i的位上的值更新为0
 * <br/>
 * void flip() : 翻转所有位的值
 * <br/>
 * boolean all() : 是否所有位都是1
 * <br/>
 * boolean one() : 是否至少有一位是1
 * <br/>
 * int count() : 返回所有位中1的数量
 * <br/>
 * String toString() : 返回所有位的状态
 * <hr/>
 * 测试链接 : https://leetcode-cn.com/problems/design-bitset/
 *
 * @author zhanghp
 * @since 2024/4/9 9:46
 */
public class Code02_DesignBitsetTest {


    static class Bitset {

        int[] bitset;

        int size;

        int ones;

        /**
         * 反转标志位：不用将所有的数都反转
         * <br/>
         * （左神的脑回路就是不一样）
         */
        boolean reverse;

        public Bitset(int size) {
            bitset = new int[(size + 31) / 32];
            this.size = size;
            reverse = false;
            ones = 0;
        }

        public void fix(int idx) {
            if (!reverse) {
                // 正常状态：0-无 1-有
                if (((bitset[idx / 32] >> (idx % 32)) & 1) != 1) {
                    ones++;
                    bitset[idx / 32] |= 1 << (idx % 32);
                }
            } else {
                // 反转状态：0-有 1-无
                if (((bitset[idx / 32] >> (idx % 32)) & 1) == 1) {
                    ones++;
                    bitset[idx / 32] &= ~(1 << (idx % 32));
                }

            }
        }

        public void unfix(int idx) {
            if (!reverse) {
                // 正常状态：0-无 1-有
                if (((bitset[idx / 32] >> idx % 32) & 1) == 1) {
                    ones--;
                    bitset[idx / 32] &= ~(1 << idx % 32);
                }
            } else {
                // 反转状态：0-有 1-无
                if (((bitset[idx / 32] >> idx % 32) & 1) == 0) {
                    ones--;
                    bitset[idx / 32] ^= (1 << idx % 32);
                }

            }
        }

        public void flip() {
            reverse = !reverse;
            ones = size - ones;
        }

        public boolean all() {
            return ones == size;

        }

        public boolean one() {
            return ones > 0;
        }

        public int count() {
            return ones;
        }

        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (int i = 0, k = 0, cur, status; i < size; k++) {
                cur = bitset[k];
                for (int j = 0; j < 32 && i < size; i++, j++){
                    status = (cur >> j) & 1;
                    status ^= reverse ? 1 : 0;
                    sb.append(status);
                }
            }
            return sb.toString();
        }
    }


}
